package edu.sjtu.grid.workflow.group;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import edu.sjtu.grid.workflow.Util;
import edu.sjtu.grid.workflow.facts.Facts;
import edu.sjtu.grid.workflow.facts.Job;
import edu.sjtu.grid.workflow.facts.Mapping;
import edu.sjtu.grid.workflow.facts.PC;
import edu.sjtu.grid.workflow.facts.Run;

public class MDP {
	
	private double unit = (double)0;
	private static int MDP_LENGTH = 2000;

	/*
	 * [job][d][pc]
	 * EFT <= d <= LFT
	*/
	private Facts facts = null;
	private GroupNode groupNode = null;
	private Run run = null;
	
	private Map<MDPKey, List<Mapping>> mapList[] = null;
	
	@SuppressWarnings("unchecked")
	public MDP(Facts facts, GroupNode groupNode, Run run)
	{
		this.facts = facts;
		this.groupNode = groupNode;
		this.run = run;
		
		if(this.facts.getGroupGraph().getUnit() > 0)
			this.unit = this.facts.getGroupGraph().getUnit();
		else
		{
			Job first = this.groupNode.getFirstJob();
			double LFT = this.groupNode.getLFT();
			double EFT = this.groupNode.getMinEFT(run, first);
			this.unit = (LFT - EFT) / MDP.MDP_LENGTH;
			//System.out.println("unit:" + this.unit);
		}
		
		this.mapList = new HashMap[this.groupNode.getJobList().size()];
		for(int i=0; i<this.mapList.length; i++)
			this.mapList[i] = new HashMap<MDPKey, List<Mapping>>();
		this.calMDP();
	}

	@SuppressWarnings("unchecked")
	private void calMDP()
	{
		List<Job> jobList = this.groupNode.getJobList();
		for(int jobI = 0; jobI < jobList.size(); jobI++) //job
		{
			Job job = jobList.get(jobI);
			Job jobBefore = (jobI == 0? null : jobList.get(jobI - 1));
			Map<MDPKey, List<Mapping>> keyToMapList = this.mapList[jobI];
			Map<MDPKey, List<Mapping>> keyToMapListJobBefore = (jobI == 0? null : this.mapList[jobI-1]);

			for(PC pc : this.facts.getPcs().getPcList())//pc
			{
				if(jobI == 0) //first job begin
				{
					double EFT = this.groupNode.getEFT(run, job, pc);
					double LFT = this.groupNode.getLFT(job);
					for(double deadline = Util.unitCeil(EFT, unit); Util.isEqualOrSmall(deadline , LFT); deadline += unit)//deadline
					{
						MDPKey key = new MDPKey(job, deadline, pc, unit);
						MDPKey keyDeadlineBefore = new MDPKey(job, deadline-unit, pc, unit);
						List<Mapping> mapList = null;
						List<Mapping> mapListDeadlineBefore = keyToMapList.get(keyDeadlineBefore);
						Mapping map = null;
						Mapping mapDeadlineBefore = (mapListDeadlineBefore == null? null : mapListDeadlineBefore.get(jobI));
						
						double f = deadline - job.getRunTime() / pc.getSpeed();
						double t = deadline;

						if(run.checkMDPMappingWithOldMappings(pc, f, t)
								&& run.checkMDPMappingWithParents(pc, job, f))
						{
							map = new Mapping(facts, job, pc, f, t);
							if(mapDeadlineBefore != null)
							{
								double costBefore = mapDeadlineBefore.getRealTransAndComputationCost(run);
								double cost = map.getRealTransAndComputationCost(run);
								if(Util.isEqualOrSmall(costBefore, cost))
									map = mapDeadlineBefore;
							}
						}
						else if(mapDeadlineBefore != null)
							map = mapDeadlineBefore;
						
						if(map != null)
						{
							mapList = new ArrayList<Mapping>();
							mapList.add(map);
							keyToMapList.put(key, mapList);
							
							/*
							System.out.print(key.toString());
							for(Mapping map2 : keyToMapList.get(key))
								System.out.println("\t" + map2.toString());*/
						}
					}//deadline
				}//first job end
				else//other job begin
				{
					double EFT = this.groupNode.getEFT(run, job, pc);
					double LFT = this.groupNode.getLFT(job);
					for(double deadline = Util.unitCeil(EFT, unit); Util.isEqualOrSmall(deadline , LFT); deadline += unit)//deadline
					{
						MDPKey key = new MDPKey(job, deadline, pc, unit);
						MDPKey keyDeadlineBefore = new MDPKey(job, deadline-unit, pc, unit);
						List<Mapping> mapList = null;
						List<Mapping> mapListDeadlineBefore = keyToMapList.get(keyDeadlineBefore);
						Mapping map = null;
						
						double f = deadline - job.getRunTime() / pc.getSpeed();
						double t = deadline;
						
						List<Mapping> bestMapListBefore = null;
						if(run.checkMDPMappingWithOldMappings(pc, f, t))
						{
							map = new Mapping(facts, job, pc, f, t);
							for(PC pcBefore : this.facts.getPcs().getPcList()) //pc before
							{
								double tt = jobBefore.getTransTime(job, pcBefore, pc);
								double deadlineBefore = Util.unitFloor(f-tt, unit);
								List<Mapping> mapListBefore = keyToMapListJobBefore.get(new MDPKey(jobBefore, deadlineBefore, pcBefore, unit));
								if(mapListBefore != null)
								{
									if(run.checkMDPMappingWithMappingList(pc, job, f, mapListBefore))
									{
										if(bestMapListBefore == null ||
												Util.isSmall(getCost(mapListBefore, map) , getCost(bestMapListBefore, map)))
											bestMapListBefore = mapListBefore;
									}
								}
							}//pc before
						}
						if((mapListDeadlineBefore != null && bestMapListBefore == null)
							||(mapListDeadlineBefore != null && bestMapListBefore != null &&
							Util.isEqualOrSmall(getCost(mapListDeadlineBefore) , getCost(bestMapListBefore, map))))
						{
							keyToMapList.put(key, mapListDeadlineBefore);
						}
						else if(bestMapListBefore != null)
						{
							mapList = (List<Mapping>) ((ArrayList<Mapping>) bestMapListBefore).clone();
							mapList.add(map);
							keyToMapList.put(key, mapList);
							
							/*
							System.out.print(key.toString());
							for(Mapping map2 : keyToMapList.get(key))
								System.out.println("\t" + map2.toString());*/
						}
					}//deadline
				}//other job end
			}//pc
			
			if(keyToMapList.isEmpty())
				return;
		}//job
	}
	
	private double getCost(List<Mapping> mappingList, Mapping map)
	{
		double cost = getCost(mappingList);
		if(!mappingList.isEmpty())
			cost += map.getRealTransAndComputationCost(mappingList.get(mappingList.size() - 1));
		return cost;
	}
	
	private double getCost(List<Mapping> mappingList)
	{
		double cost = 0;
		if(mappingList == null || mappingList.isEmpty())
			return cost;
		cost += mappingList.get(0).getRealTransAndComputationCost(run);
		for(int i=1; i<mappingList.size(); i++)
			cost += mappingList.get(i).getRealTransAndComputationCost(mappingList.get(i-1));
		return cost;
	}
	
	public List<GroupMapping> getGroupMappingList()
	{
		Map<MDPKey, List<Mapping>> map = this.mapList[this.groupNode.getJobList().size() - 1];
		if(map == null || map.isEmpty())
			return null;

		ArrayList<GroupMapping> groupMappingList = new ArrayList<GroupMapping>();
		for(PC pc : this.facts.getPcs().getPcList())
		{
			Job job = this.groupNode.getLastJob();
			double LFT = this.groupNode.getLFT(job);
			double EFT = this.groupNode.getEFT(run, job, pc);
			List<Mapping> last = null;
			for(double deadline = Util.unitCeil(EFT, unit); Util.isEqualOrSmall(deadline , LFT); deadline += unit)
			{
				MDPKey key = new MDPKey(job, deadline, pc, unit);
				List<Mapping> tmp = map.get(key);
				if(tmp != null && checkEqual(last, tmp) == false)
					groupMappingList.add(new GroupMapping(run, groupNode, tmp));
				last = tmp;
			}
		}
		
		Collections.sort(groupMappingList, new GroupMappingComparator());
		
		return groupMappingList;
	}
	
	private boolean checkEqual(List<Mapping> map1, List<Mapping> map2)
	{
		if(map1 == null || map2 == null)
			return false;
		if(map1.size() != map2.size())
			return false;
		for(int i=0; i<map1.size(); i++)
		{
			if(map1.get(i).equals2(map2.get(i)) == false)
				return false;
			if(!Util.isEqual(getCost(map1), getCost(map2)))
				return false;
		}
		return true;
	}
	
	private class GroupMappingComparator implements Comparator<GroupMapping>{
		@Override
		public int compare(GroupMapping arg0, GroupMapping arg1) {
			if(Util.isBig(getCost(arg0.getMappingList()) , getCost(arg1.getMappingList())))
				return 1;
			else
				return -1;
		}
	}
}
